home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / comnumb.exe / RATIONAL.CPP < prev    next >
C/C++ Source or Header  |  1992-05-01  |  10KB  |  399 lines
  1. ////////////////////////////////////////////////////////////////
  2. // rational.cpp: Rational number class implementation.
  3. // Copyright(c) 1992 Azarona Software. All rights reserved.
  4. // NOTE: Many of the routines here could be made inline for
  5. // significant performance gains.
  6. ////////////////////////////////////////////////////////////////
  7. #include <ctype.h>
  8. #include "rational.h"
  9.  
  10. long Gcd(long n, long d)
  11. // Returns the greatest common divisor of |n| and |d|. 
  12. // Note: This routine will return 0 if both n and d are zero.
  13. {
  14.   if (n < 0) n = -n;
  15.   if (d < 0) d = -d;
  16.   while(d > 0) {
  17.     long r = n % d;
  18.     n = d;
  19.     d = r;
  20.   }
  21.   return n;
  22. }
  23.  
  24. istream &operator>>(istream &s, Rational &r)
  25. // Reads in a rational number either as <n/d> or w, 
  26. // where w is a whole number. Appropriate whitespace
  27. // is allowed. If the stream s is not in a good state upon 
  28. // return, then r will contain <0/0>.
  29. {
  30.   char c;
  31.  
  32.   if (s >> c) { // Read in first non-whitespace character
  33.      if (isdigit(c) || (c == '-') || (c == '+')) {
  34.         // We have a whole number. Put back character
  35.         // and then read in the whole number.
  36.         s.putback(c);
  37.         if (s >> r.n) {
  38.            r.d = 1; // Now we have proper fraction
  39.         }
  40.      }
  41.      else if (c == '<') {
  42.         // Reading in <n/d> syntax
  43.         if (s >> r.n) { // We've got numerator
  44.            if (s >> c) { // Look for '/'
  45.               if (c == '/') {
  46.                  if (s >> r.d) { // We've got denominator
  47.                      r.Simplify();
  48.                      if (s >> c) { // Look for '>'
  49.                         // Syntax error?
  50.                         if (c != '>') s.clear(ios::failbit);
  51.                      }
  52.                  }
  53.               }
  54.               else {
  55.                 s.clear(ios::failbit); // Signal syntax error
  56.               }
  57.            }
  58.         }
  59.      }
  60.      else s.clear(ios::failbit); // Signal syntax error
  61.   }
  62.   if (!s) { // Stream failure, so result is undefined
  63.      r.n = 0; r.d = 0; 
  64.   }
  65.   return s;
  66. }
  67.  
  68. ostream &operator<<(ostream &s, const Rational &r)
  69. // Output rational number r to stream. Outputs "und" 
  70. // for <0/0>. If denominator is 1, it is not shown.
  71. {
  72.   if (r.d == 0) return s << "und";  // Undefined number
  73.   if (r.d == 1) return s << r.n;    // Output whole number
  74.   return s << '<' << r.n << '/' << r.d << '>';
  75. }
  76.  
  77. Rational::Rational()
  78. // Default constructor sets the number to be undefined.
  79. : n(0), d(0)
  80. {
  81.   // Nothing else to do
  82. }
  83.  
  84. Rational::Rational(long u)
  85. // Rational number becomes whole number u.
  86. : n(u), d(1)
  87. {
  88.   // Nothing else to do
  89. }
  90.  
  91. Rational::Rational(long u, long v)
  92. // General constructor initializing number to <u/v>.
  93. {
  94.   Set(u, v);
  95. }
  96.  
  97. Rational::Rational(const Rational &r)
  98. // Copy constructor.
  99. : n(r.n), d(r.d)
  100. {
  101.   // Nothing else to do
  102. }
  103.  
  104. long Rational::Numerator() const
  105. {
  106.   return n;
  107. }
  108.  
  109. long Rational::Denominator() const
  110. {
  111.   return d;
  112. }
  113.  
  114. int Rational::IsUndefined() const
  115. {
  116.   return d == 0;
  117. }
  118.  
  119. int Rational::IsPositive() const
  120. {
  121.   return n > 0;
  122. }
  123.  
  124. int Rational::IsNegative() const
  125. {
  126.   return n < 0;
  127. }
  128.  
  129. int Rational::IsZero() const
  130. {
  131.   return n == 0 && d != 0;
  132. }
  133.  
  134. void Rational::Simplify()
  135. // Simplifies the rational number to have the smallest numerator 
  136. // and denominator possible. Also, if the number is negative, 
  137. // the numerator carries the sign. Also, all numbers of the 
  138. // form <x/0> are normalized to <0/0>, which represents 
  139. // "undefined".
  140. {
  141.   if (d != 0) {
  142.     // Simplify the numerator and denominator
  143.     long gcd = Gcd(n, d);
  144.     n /= gcd;
  145.     d /= gcd;
  146.     if (d < 0) {
  147.        // Keep negative sign in numerator. This also has
  148.        // a nice side effect of eliminating the sign if
  149.        // both n and d are negative.
  150.        n = -n;
  151.        d = -d;
  152.     }
  153.   }
  154.   else n = 0; // So we have <0/0>
  155. }
  156.  
  157. void Rational::Set(long u, long v)
  158. // Sets rational number to <u/v>, simplifying
  159. // the result.
  160. {
  161.   n = u; d = v; Simplify();
  162. }
  163.  
  164. void Rational::Negate()
  165. // Take the negative of this number.
  166. {
  167.   n = -n;
  168. }
  169.  
  170. void Rational::Invert()
  171. // Flip numerator and denominator
  172. {
  173.   long t = n;
  174.   if (n < 0) { // Keep sign in numerator
  175.      n = -d;
  176.      d = -t;
  177.   }
  178.   else {
  179.      n = d;
  180.      d = t;
  181.   }
  182.   if (d == 0) n = 0; // Might have <x/0>, so set to <0/0>
  183. }
  184.  
  185. long Rational::RemoveWholePart()
  186. // If |this| > 1, remove the whole number part,
  187. // so that |this| < 1. Return the whole number.
  188. {
  189.   long w;
  190.   if (d == 0) { // Undefined number
  191.      w = 0;     // (w can be anything, why not zero?)
  192.   }
  193.   else {
  194.     w = n / d; // Get whole part...
  195.     n -= w*d;  // Remove from number.
  196.   }
  197.   return w;
  198. }
  199.  
  200. Rational &Rational::operator=(const Rational &r)
  201. // Assignment operator.
  202. {
  203.   n = r.n; d = r.d; return *this;
  204. }
  205.  
  206. Rational Rational::operator-() const
  207. // Unary - operator. Computes negative of this number
  208. // and returns a copy.
  209. {
  210.   return Rational(-n, d);
  211. }
  212.  
  213. Rational Rational::operator+() const
  214. // Unary + operator. Returns a copy of this number.
  215. // (Thus, semantics are consistent with unary -).
  216. {
  217.   return Rational(*this);
  218. }
  219.  
  220. Rational &Rational::operator+=(const Rational &r)
  221. // Adds r to this number. Stores the result in this number.
  222. {
  223.   return operator=(*this + r);
  224. }
  225.  
  226. Rational &Rational::operator-=(const Rational &r)
  227. // Subtracts r from this number. Stores the result in 
  228. // this number.
  229. {
  230.   return operator=(*this - r);
  231. }
  232.  
  233. Rational &Rational::operator*=(const Rational &r)
  234. // Mutliplies this number by r. Stores the result in 
  235. // this number.
  236. {
  237.   return operator=(*this * r);
  238. }
  239.  
  240. Rational &Rational::operator/=(const Rational &r)
  241. // Divides this number by r. Stores the result in 
  242. // this number.
  243. {
  244.   return operator=(*this / r);
  245. }
  246.  
  247. Rational &Rational::operator++()
  248. // Prefix increment operator. Safe to use
  249. // in expressions like ++(++r).
  250. {
  251.   return *this += 1;
  252. }
  253.  
  254. Rational &Rational::operator--()
  255. // Prefix decrement operator. Safe to use
  256. // in expressions like --(--r).
  257. {
  258.   return *this -= 1;
  259. }
  260.  
  261. Rational Rational::operator++(int)
  262. // Postfix increment. Note that we don't return a reference
  263. // as we do with prefix increment. Instead a copy of the result
  264. // is returned. Thus, expressions like (r++)++ will not return
  265. // the correct result.
  266. // WARNING: Result not checked for possible overflow.
  267. {
  268.   Rational old(*this); 
  269.   *this += 1;
  270.   return old;
  271. }
  272.  
  273. Rational Rational::operator--(int)
  274. // Postfix decrement. Note that we don't return a reference
  275. // as we do with prefix decrement. Instead a copy of the result
  276. // is returned. Thus, expressions like (r--)-- will not return
  277. // the correct result.
  278. // WARNING: Result not checked for possible overflow.
  279. {
  280.   Rational old(*this);
  281.   *this -= 1;
  282.   return old;
  283. }
  284.  
  285. Rational operator+(const Rational &a, const Rational &b)
  286. // Adds a to b and returns the result. See Knuth Vol 2 for 
  287. // explanation on the method used here to do the addition, 
  288. // which carefully avoids (but does not eliminate) overflow. 
  289. // This method also automatically simplifies the result. 
  290. // If one operand is undefined, the result is undefined.
  291. // WARNING: Result not checked for possible overflow.
  292. {
  293.   Rational r;
  294.   long t, d1, d2;
  295.  
  296.   if (a.d == 0 || b.d == 0) { // Undefined operand?
  297.      r.n = 0; r.d = 0; // So we have <0/0>
  298.   }
  299.   else {
  300.     d1 = Gcd(a.d, b.d);
  301.     if (d1 == 1) {
  302.        r.n = a.n*b.d + a.d*b.n;
  303.        r.d = a.d*b.d;
  304.     }
  305.     else {
  306.        t = a.n*(b.d/d1) + b.n*(a.d/d1);
  307.        d2 = Gcd(t, d1);
  308.        r.n = t / d2;
  309.        r.d = (a.d/d1) * (b.d/d2);
  310.     }
  311.   }
  312.   return r;
  313. }
  314.  
  315. Rational operator-(const Rational &a, const Rational &b)
  316. // Subtracts b from a and returns result. Uses the
  317. // operator+() function to do the dirty work.
  318. // WARNING: Result not checked for possible overflow.
  319. {
  320.   Rational nb(b); // Note: We are avoiding a call to
  321.   nb.Negate();    // Simplify() here.
  322.   return a + nb;  // Ie: a + (-b)
  323. }
  324.  
  325. Rational operator*(const Rational &a, const Rational &b)
  326. // Multiplies a and b together and returns result. 
  327. // Method used is ala Knuth: Vol. 2, which carefully 
  328. // avoids